package com.peng.leetcode.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * FindWhetherExistsPath
 *
 * 面试题 04.01. 节点间通路
 *
 * @author: lupeng6
 * @create: 2021/1/29 19:31
 */
public class FindWhetherExistsPath {

    public static void main(String[] args) {
        int n = 12;
        int[][] graph = {{0, 1}, {1, 2}, {1, 3}, {1, 10}, {1, 11}, {1, 4}, {2, 4}, {2, 6}, {2, 9}, {2, 10}, {2, 4}, {2, 5}, {2, 10}, {3, 7}, {3, 7}, {4, 5}, {4, 11}, {4, 11}, {4, 10}, {5, 7}, {5, 10}, {6, 8}, {7, 11}, {8, 10}};
        int start =2, target = 3;
        System.out.println(new FindWhetherExistsPath().findWhetherExistsPath(n, graph, start, target));
    }


    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        List<List<Integer>> adjacency = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            adjacency.add(new ArrayList<>());
        }
        for (int i = 0; i < graph.length; i++) {
            adjacency.get(graph[i][0]).add(graph[i][1]);
        }
//        for (int[] ints : graph) {
//            adjacency.get(ints[0]).add(ints[1]);
//        }

        return dfs(adjacency, start, target);
    }

    private boolean dfs(List<List<Integer>> adjacency, int start, int target) {
        List<Integer> next = adjacency.get(start);
        if (next.contains(target)) {
            return true;
        }
        for (Integer nextVertex : next) {
            if (dfs(adjacency, nextVertex, target)) {
                return true;
            }
        }
        return false;
    }
}
